package com.bstree;

/**
 * @Author: sy
 * @Date: 2021/3/23 22:57
 * @Description:
 */
public class BsTree {

    public BsTreeNode search(BsTreeNode root, int value) {
        if (root == null) {
            return null;
        }
        if (root.val > value) {
            return search(root.left, value);
        } else if (root.val < value) {
            return search(root.right, value);
        } else {
            return root;
        }
    }

    public boolean insertNode(BsTreeNode root, BsTreeNode nodeInserted) {
        if (root == null) {
            root = nodeInserted;
            return true;
        }
        if (root.val > nodeInserted.val) {
            // 根的值大于插入节点的值，往左找
            if (root.left == null) {
                root.left = nodeInserted;
                nodeInserted.parent = root;
                return true;
            } else {
                return insertNode(root.left, nodeInserted);
            }
        } else if (root.val < nodeInserted.val) {
            if (root.right == null) {
                root.right = nodeInserted;
                nodeInserted.parent = root;
                return true;
            } else {
                return insertNode(root.right, nodeInserted);
            }
        } else {
            return false;
        }
    }

    public void deleteNode(BsTreeNode root, int value) {
        if (root == null) {
            return;
        }
        if (root.val > value) {
            deleteNode(root.left, value);
        } else if (root.val < value) {
            deleteNode(root.right, value);
        } else {
            // 找到了要删除的节点
            // 第一种情况，左右子树均为空，直接删除
            if (root.left == null && root.right == null) {
                if (root.parent.left == root) {
                    root.parent.left = null;
                } else {
                    root.parent.right = null;
                }
                root.parent = null;
            }
            // 第二种情况，待删除节点只有左子树，用待删除节点的左子树替换掉删除节点
            else if (root.right == null) {
                BsTreeNode rootLeft = root.left;
                root.left = rootLeft.left;
                root.right = rootLeft.right;
                root.val = rootLeft.val;
                // 修正parent引用
                if (root.left != null) {
                    root.left.parent = root;
                } else if (root.right != null) {
                    root.right.parent = root;
                }
            }
            // 第三种情况，待删除节点只有右子树，用待删除节点的右子树替换掉删除节点
            else if (root.left == null) {
                BsTreeNode rootRight = root.right;
                root.right = rootRight.right;
                root.left = rootRight.left;
                root.val = rootRight.val;

                if (root.left != null) {
                    root.left.parent = root;
                } else if (root.right != null) {
                    root.right.parent = root;
                }
            }
            // 第四种情况，左右子树都不为空，用待删除节点的前驱或后继节点代替待删除节点，对前驱或后继节点做删除操作
            else {
                // 找到当前节点的中序前驱节点
                BsTreeNode node = root.left;
                while (node.right != null) {
                    node = node.right;
                }
                // 节点内容替换
                root.val = node.val;
                // 删除前驱节点
                deleteNode(node, node.val);
            }
        }
    }
}
